//
// Created by tacom on 22-9-10.
//
// web example: https://heather.cs.ucdavis.edu/~matloff/OpenMP/Examples/NM/Dijkstra.c

#include "cstdio"
#include "omp.h"  // 如果只用预定义宏的话，不需要导入

#define LARGEINT 2 << (30 - 1)
#define NV 6

// global variable, shared by all thread
int ohd[NV][NV],  // distance between vertices
    mind[NV],     // min distance found
    notdone[NV],  // not checked vertices
    nth,          // number of threads
    chunk,        // number of vertices handled by each thread
    md,           // current min over all threads
    mv;           // vertex which achieves are min


void init(int ac, char **av){
    int i, j;
    for(i = 0; i < NV; ++i){
        for(j = 0; j < NV; ++j){
            if(i == j) ohd[i][j] = 0;
            else ohd[i][j] = LARGEINT;
        }
    }
    ohd[0][1] = ohd[1][0] = 40;
    ohd[0][2] = ohd[2][0] = 15;
    ohd[1][2] = ohd[2][1] = 20;
    ohd[1][3] = ohd[3][1] = 10;
    ohd[2][3] = ohd[3][2] = 100;
    ohd[1][5] = ohd[5][1] = 6;
    ohd[4][5] = ohd[5][4] = 8;
    for(i = 1; i < NV; ++i){
        notdone[i] = 1;
        mind[i] = ohd[0][i];
    }
}

void findmymin(int s, int e, int *d, int *v){
    // find closest to 0 among not done, among s throght e
    int i;
    *d = LARGEINT;
    for(i = s; i <= e; ++i){
        if(notdone[i] && mind[i] < *d){
            *d = ohd[0][i];
            *v = i;
        }
    }
}

void updateohd(int s, int e){
    int i;
    for(i = s; i <= e; ++i){
        if (mind[mv] + ohd[mv][i] < mind[i])
            mind[i] = mind[mv] + ohd[mv][i];
    }
}

void dowork(){
    // translates progmas to threads calls
    #pragma omp parallel
    {
        int startv, endv,  // start, end vertices for this thread
            step,          // whole procedure goes NV steps
            mymd,          // min value found by this thread
            mymv,          // vertex which attains that value
            me = omp_get_thread_num();  // my thread number

        // single mean that only one thread(first reach) do this block
        #pragma omp single
        {
            nth = omp_get_num_threads();
            chunk = nth;
            printf("there are %d threads\n", nth);
        }

        startv = me * chunk;
        endv = startv + chunk - 1;
        for(step = 0; step < NV; ++step){
            // find closest vertex to 0 among not done
            #pragma omp single
            {
                md = LARGEINT;
                mv = 0;
            }
            findmymin(startv, endv, &mymd, &mymv);
            // update if mine is smaller
            // critical sets up a critical section, mean lock/unlock operations
            // one-statement critical sections can write below:
            // #pragma omp atomic
            // y += x;
            #pragma omp critical
            {
                if (mymd < md){
                    md = mymd;
                    mv = mymv;
                }
            }
            // mark new vertex as done
            #pragma omp single
            { notdone[mv] = 0; }
            // barrier, like cudaThreadsSync();
            #pragma omp barrier
        }
    }
}

int main(int argc, char **argv){
    int i;
    init(argc, argv);
    dowork();
    printf("min distance: \n");
    for(i = 1; i < NV; ++i){
        printf("%d\n", mind[i]);
    }
}